DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2022.37

Space-Stretch Tradeoff in Routing Revisited

Authors: Anatoliy Zinovyev

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract

We present several new proofs of lower bounds for the space-stretch tradeoff in labeled network routing. First, we give a new proof of an important result of Cyril Gavoille and Marc Gengler that any routing scheme with stretch < 3 must use Ω(n) bits of space at some node on some network with n vertices, even if port numbers can be changed. Compared to the original proof, our proof is significantly shorter and, we believe, conceptually and technically simpler. A small extension of the proof can show that, in fact, any constant fraction of the n nodes must use Ω(n) bits of space on some graph. Our main contribution is a new result that if port numbers are chosen adversarially, then stretch < 2k+1 implies some node must use Ω(n^(1/k) log n) bits of space on some graph, assuming a girth conjecture by Erdős. We conclude by showing that all known methods of proving a space lower bound in the labeled setting, in fact, require the girth conjecture.

Cite as

Anatoliy Zinovyev. Space-Stretch Tradeoff in Routing Revisited. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{zinovyev:LIPIcs.DISC.2022.37,
  author =	{Zinovyev, Anatoliy},
  title =	{{Space-Stretch Tradeoff in Routing Revisited}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.37},
  URN =		{urn:nbn:de:0030-drops-172281},
  doi =		{10.4230/LIPIcs.DISC.2022.37},
  annote =	{Keywords: Compact routing, labeled network routing, lower bounds}
}

Search Results

Documents authored by Zinovyev, Anatoliy

Space-Stretch Tradeoff in Routing Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message